/**
 * Definition for singly-linked list.
 */
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
public:
    // 简单：可以保留一个
    // 单指针即可实现
    ListNode* deleteDuplicatesSimple(ListNode* head) {
        if (!head || !head->next) return head;
        ListNode* curr = head;
        while (curr->next) {
            if (curr->val == curr->next->val) {
                curr->next = curr->next->next;
            } else {
                curr = curr->next;
            }
        }
        return head;
    }

    // 将出现过重复的元素全部移除（包括首个）
    // 注意 >2 次的出现
    // 经典：使用三指针：prev, curr, next
    ListNode* deleteDuplicates(ListNode* head) {
        if (!head || !head->next) return head;
        ListNode* dummyNode = new ListNode(-1);
        dummyNode->next = head;
        ListNode* curr = head, * prev = dummyNode, * next = curr->next;
        bool del = false;  // [需要删除第一个重复节点]的状态
        while (next) {
            if (curr->val == next->val) {
                next = next->next;
                curr->next = next;  // 完成删除
                del = true;
            } else if (del) {  // 需要删除第一个重复的
                curr = next;
                next = next->next;
                prev->next = curr;  // 完成删除操作
                del = false;  // 重置为无需删除的状态
            } else {
                prev = curr;
                curr = next;
                next = next->next;
            }
        }
        if (del) prev->next = next;
        return dummyNode->next;
    }
};
